We proposed a one-way trapdoor permutation f based multi-signature scheme which can keep tighter reduction rate. Assuming the underlying hash functions are ideal, our proposed scheme is not only provably secure, but are so in a tight. An ability to forge multi-signatures with a certain amount of computational resources implies the ability to invert a one-way trapdoor permutation f (on the same size modulus) with about the same computational effort. The proposed scheme provides the exact security against Adaptive-Chosen-Message-Attack and Adaptive-Insider-Attack by . can also attack in key generation phase, and act in collusion with corrupted signers.

Although a great deal of research has been done on electronic cash schemes with blind multisignatures to prevent an insider attack, there is no discussion of a formal security model in the literature. Firstly we discussed the security model of e-cash schemes based on the blind multisignature scheme against a (restricted) attack model and proposed a concrete scheme proven to be secure in the model [1]; however, this attack model disallows an attacker from corrupting an issuing bank and shops in the forgery game. In this paper, first, we reconsider the security model to remove the restriction of the attack model. Second, we propose a new untraceable e-cash scheme with a blind multisignature scheme and prove that the proposed scheme is secure against the (non-restricted) attacks under the DDH assumption in the random oracle model.

Maurer and Yacobi proposed an ID-Based key distribution scheme in 1991. In this scheme, the private key for each user is generated by solving discrete logarithm problem. We examine the realizability of this scheme. We show that this scheme can be practical by appropriate parameter setting.

This paper describes the design principles, the specification, and evaluations of a new 128-bit block cipher E2, which was proposed to the AES (Advanced Encryption Standard) candidates. This algorithm supports 128-bit, 192-bit, and 256-bit secret keys. The design philosophy of E2 is highly conservative; the structure uses 12-round Feistel as its main function whose round function is constructed with 2-round SPN structure, and initial/final transformational functions. E2 has practical security against differential attack, linear attack, cryptanalysis with impossible differential, truncated differential attack, and so on. Furthermore, E2 can be implemented efficiently and flexibly on various platforms because the primitive operations involve byte length processing.

This work focuses on a vulnerability of hash functions due to sloppy usages or implementations in the real world. If our cryptographic research community succeeded in the development of a perfectly secure random function as the random oracle, it might be broken in some sense by invalid uses. In this paper, we propose a new variant of the random oracle model in order to analyze the security of cryptographic protocols under the situation of an invalid use of hash functions. Our model allows adversaries to obtain contents of the hash list of input and output pairs arbitrarily. Also, we analyze the security of several prevailing protocols (FDH, OAEP, Cramer-Shoup cryptosystem, Kurosawa-Desmedt cryptosystem, NAXOS) in our model. As the result of analyses, we clarify that FDH and Cramer-Shoup cryptosystem are still secure but others are insecure in our model. This result shows the separation between our model and the standard model.

At Eurocrypt'05, Wang et al. presented efficient collision attacks on MD5 and MD4 hash functions. They found a collision of MD5 with a complexity of less than 237 MD5 hash operations, and a collision of MD4 with complexity less than 28 MD4 hash operations. In their attack, the procedure to generate a collision is divided into 4 steps. First, they determine the message differential and output differentials of chaining variables in each step, which generates a collision with small complexity. Second, they construct sufficient conditions that guarantee that the desired differential is always calculated. Third, they find a message modification that can satisfy the sufficient conditions with high probability. Finally, they search for a message that satisfies all sufficient conditions. In this paper, we focus on the message modification of MD5 and MD4, and propose a new message modification. Using our message modification, a collision of MD5 can be found with complexity less than 229 MD5 hash operations, and a collision of MD4 can be found with complexity less than 3 MD4 hash operations. To improve the complexity from previous attacks, we mainly use two ideas. The first idea is to use message modification that can satisfy more sufficient conditions in the second round than in previous attacks. The second idea is to use message modification that can enable us to search for a collision starting from an intermediate step.

We first model the formal security model of multisignature scheme following that of group signature scheme. Second, we prove that the following three probabilistic multisignature schemes based on a trapdoor permutation have tight security; PFDH (probabilistic full domain hash) based multisignature scheme (PFDH-MSS), PSS (probabilistic signature scheme) based multisignature scheme (PSS-MSS), and short signature PSS based multisignature scheme (S-PSS-MSS). Third, we give an optimal proof (general result) for multisignature schemes, which derives the lower bound for the length of random salt. We also estimate the upper bound for the length in each scheme and derive the optimal length of a random salt. Two of the schemes are promising in terms of security tightness and optimal signature length. In appendix, we describe a multisignature scheme using the claw-free permutation and discuss its security.

Hash functions are used to compress messages into digital signatures. A hash function has to be collision free; i.e., it must be computationally infeasible to construct different messages which output the same hash-value. This paper shows that five of the hash functions for digital signatures that are being discussed in ISO Standardization activities and/or recently proposed are not collision free. These hash functions are analyzed from the standpoints of their structure, the complementation property and the weak keys of the block ciphers used in them. As a result, it is clear that many pairs of messages can be created to generate the same hash-values. Therefore, the hash functions analyzed here are recommended to be revised or replaced by new ones that are collision free.

In CRYPTO '94, Langford and Hellman attacked DES reduced to 8-round in the chosen plaintext scenario by their "differential-1inear cryptanalysis," which is a combination of differential cryptanalysis and linear cryptanalysis. In this paper, a historical review of differential-linear cryptanalysis, our formalization of differential-linear cryptanalysis, and the application of differential-linear cryptanalysis to FEAL-8 are presented. As a result, though the previous best method (differential cryptanalysis) required 128 chosen plaintexts, only 12 chosen plaintexts are sufficient, in computer experimentations, to attack FEAL-8.

We first model the variants of OAEP and SAEP by changing a construction and position of a redundancy, and establish a universal proof technique in the random oracle model, the comprehensive event dividing tree. We then make a taxonomical security consideration of the variants of OAEP and SAEP, based on the assumptions of one-wayness and partial-domain one-wayness of the encryption permutation, by applying the tree. Furthermore, we demonstrate the concrete attack procedures against all insecure schemes; we insist that the security proof failure leads to some attacks. From the security consideration, we find that one of the variants leads to a scheme without the redundancy; the scheme is not PA (plaintext aware) but IND-CCA2 secure. Finally, we conclude that some of them are practical in terms of security tightness and short bandwidth.

Card-based cryptography realizes secure multiparty computation using physical cards. In 2018, Watanabe et al. proposed a card-based three-input majority voting protocol using three cards. In a card-based cryptographic protocol with n-bit inputs, it is known that a protocol using shuffles requires at least 2n cards. In contrast, as Watanabe et al.'s protocol, a protocol using private permutations can be constructed with fewer cards than the lower bounds above. Moreover, an n-input protocol using private permutations would not even require n cards in principle since a private permutation depending on an input can represent the input without using additional cards. However, there are only a few protocols with fewer than n cards. Recently, Abe et al. extended Watanabe et al.'s protocol and proposed an n-input majority voting protocol with n cards and n + ⌊n/2⌋ + 1 private permutations. This paper proposes an n-input majority voting protocol with ⌈n/2⌉ + 1 cards and 2n-1 private permutations, which is also obtained by extending Watanabe et al.'s protocol. Compared with Abe et al.'s protocol, although the number of private permutations increases by about n/2, the number of cards is reduced by about n/2. In addition, unlike Abe et al.'s protocol, our protocol includes Watanabe et al.'s protocol as a special case where n=3.

As one of the logic-level countermeasures against DPA (Differential Power Analysis) attacks, Random Switching Logic (RSL) was proposed by Suzuki, Saeki and Ichikawa in 2004 . The RSL technique was applied to AES hardware and a prototype chip was implement with a 0.13-µm standard CMOS library for evaluating the DPA resistance . Although the main purpose of using RSL is to resist the DPA attacks, our experimental results of Clock-based Fault Analysis (CFA) show that one can reveal the secret information from the prototype chip. This paper explains the mechanism of the CFA attack and discusses the reason for the success of the attack against a prototype implementation of AES with RSL (RSL-AES). Furthermore, we consider an ideal RSL-AES implementation that counteracts the CFA attacks.

This paper applies linear cryptanalysis to FEAL and describes the experimental results of attacking FEAL-8 by linear cryptanalysis. The following points are important in linear cryptanalysis to reduce the processing amount and memory size in the attack: 1) to find linear expressions with as high a deviation as possible, and 2) to reduce the number of effective key bits and effective text bits. We have succeeded in attacking FEAL-8 in about 1 hour on a low-end workstation (SPARCstation 10 Model 30). We have confirmed that the entire set of subkeys of FEAL-8 can be derived from 225 known plaintexts with a success rate of over 70%, and from 226 known plaintexts with a success rate of almost 100%.

This paper describes two attacks against blind decryption (decode) based on the commutative random-self reducibility and RSA systems utilizing the transformability of digital signatures proposed in [2]. The transformable digital signature was introduced in [2],[8] for defeating an oracle attack, where the decrypter could be abused as an oracle to release useful information for an attacker acting as a requester of blind decryption. It was believed in [2],[8] that the correctness of a query to an oracle was ensured by the transformable signature derived from an original signature issued by the decrypter in advance, and a malicious query to an oracle could be detected before the blind decryption by the decrypter or would lead to release no useful information to an attacker. The first attack can decrypt all encrypted data with one access to an oracle. The second one generates a valid signature for an arbitrary message selected by an attacker abusing the validation check procedure.

We propose a new hidden vector encryption (HVE) scheme that we call a ciphertext-policy delegatable hidden vector encryption (CP-dHVE) scheme. Several HVE schemes have been proposed and their properties have been analyzed extensively. Nonetheless, the definition of the HVE has been left unchanged. We therefore reconsider it, and point out that the conventional HVE should be categorized as the key-policy HVE, because the vectors corresponding to the secret keys can contain wildcards (which specify an access policy) whereas those corresponding to the ciphertexts cannot contain them. We then formalize its dual concept, the ciphertext-policy HVE, and propose a concrete scheme. Then, as an application of our scheme, we propose a public-key encryption with conjunctive keyword search scheme that can be used in the hierarchical user systems. Our scheme is novel in that the ciphertext size grows logarithmically to the number of uses in the system, while that of a conventional scheme grows linearly.

Dr. Kenji Koyama, one of the most respected and prominent Japanese researchers in modern cryptography, passed away on March 27, 2000. He left behind him many outstanding academic achievements in cryptography as well as other areas such as emotion transmission theory, learning and mathematical games. In this manuscript, with our deepest sympathy and greatest appreciation for his contribution to our society, we introduce his major works mainly in cryptography, although his papers in other areas are included in the bibliography list.

In 2005, collision resistance of several hash functions was broken by Wang et al. The strategy of determining message differences is the most important part of collision attacks against hash functions. So far, many researchers have tried to analyze Wang et al.'s method and proposed improved collision attacks. Although several researches proposed improved attacks, all improved results so far were based on the same message differences proposed by Wang et al. In this paper, we propose new message differences for collision attacks on MD4 and MD5. Our message differences of MD4 can generate a collision with complexity of less than two MD4 computations, which is faster than the original Wang et al.'s attack, and moreover, than the all previous attacks. This is the first result that improves the complexity of collision attack by using different message differences from Wang et al.'s. Regarding MD5, so far, no other message difference from Wang et al.'s is known. Therefore, study for constructing method of other message differences on MD5 should be interesting. Our message differences of MD5 generates a collision with complexity of 242 MD5 computations, which is slower than the latest best attack. However, since our attack needs only 1 bit difference, it has some advantages in terms of message freedom of collision messages.

In this paper we propose an algorithm of factoring any integer N which has k different prime factors with the same bit-length, when about ()log2 N high-order bits of each prime factor are given. For a fixed ε, the running time of our algorithm is heuristic polynomial in (log2 N). Our factoring algorithm is based on a lattice-based algorithm of solving any k-variate polynomial equation over Z, which might be an independent interest.

Most aggregate signature schemes are relying on pairings, but high computational and storage costs of pairings limit the feasibility of those schemes in practice. Zhao proposed the first pairing-free aggregate signature scheme (AsiaCCS 2019). However, the security of Zhao's scheme is based on the hardness of a newly introduced non-standard computational problem. The recent impossibility results of Drijvers et al. (IEEE S&P 2019) on two-round pairing-free multi-signature schemes whose security based on the standard discrete logarithm (DL) problem have strengthened the view that constructing a pairing-free aggregate signature scheme which is proven secure based on standard problems such as DL problem is indeed a challenging open problem. In this paper, we offer a novel solution to this open problem. We introduce a new paradigm of aggregate signatures, i.e., aggregate signatures with an additional pre-communication stage. In the pre-communication stage, each signer interacts with the aggregator to agree on a specific random value before deciding messages to be signed. We also discover that the impossibility results of Drijvers et al. take effect if the adversary can decide the whole randomness part of any individual signature. Based on the new paradigm and our discovery of the applicability of the impossibility result, we propose a pairing-free aggregate signature scheme such that any individual signature includes a random nonce which can be freely generated by the signer. We prove the security of our scheme based on the hardness of the standard DL problem. As a trade-off, in contrast to the plain public-key model, which Zhao's scheme uses, we employ a more restricted key setup model, i.e., the knowledge of secret-key model.